package com.ztom.daily.n2022.m3;

/**
 * 图片平滑器
 * <p>
 * https://leetcode-cn.com/problems/image-smoother/
 *
 * @author ZhangTao
 */
public class Day24ImageSmoother {

    public int[][] imageSmoother1(int[][] img) {
        if (img == null || img.length == 0 || img[0].length == 0) {
            return null;
        }
        int m = img.length;
        int n = img[0].length;
        int[][] res = new int[m][n];

        int[][] dirs = {
                {0, 0},
                {0, 1}, {0, -1},
                {1, 0}, {-1, 0},
                {1, 1}, {-1, 1},
                {-1, -1}, {1, -1}
        };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算当前位置的答案
                int sum = 0;
                int count = 0;
                for (int[] dir : dirs) {
                    // 当前坐标
                    int x = i + dir[0];
                    int y = j + dir[1];
                    // 检查越界
                    if (x < 0 || x >= m || y < 0 || y >= n) {
                        continue;
                    }
                    sum += img[x][y];
                    count++;
                }
                res[i][j] = sum / count;
            }
        }
        return res;
    }

    public int[][] imageSmoother(int[][] img) {
        if (img == null || img.length == 0 || img[0].length == 0) {
            return null;
        }
        int m = img.length;
        int n = img[0].length;
        int[][] res = new int[m][n];

        // 二维前缀和 [i, j] 代表的是 [i - 1, j - 1] 的和
        int[][] preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + img[i - 1][j - 1];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算当前位置的答案
                int l = Math.max(0, j - 1);
                int r = Math.min(n - 1, j + 1);
                int t = Math.max(0, i - 1);
                int b = Math.min(m - 1, i + 1);
                int count = (r - l + 1) * (b - t + 1);
                // 右下角 - 左上角
                int sum = preSum[b + 1][r + 1] - preSum[t][r + 1] - preSum[b + 1][l] + preSum[t][l];

                res[i][j] = sum / count;
            }
        }
        return res;
    }
}
